%
% Section for introduction
%
\section{Design}
\label{sec:Design}
As mentioned in the introduction, the proposed system gathers, associates, and organizes temporal information related to the input person entity from documents present on the Web. To begin developing a solution to the stated problem, the design of ChronoSearch starts by breaking the problem into the following sub problems:

\begin{description}
\item{Extracting temporal information.} The system must be capable of extracting and resolving temporal information that exists in various formats within web pages.
\item{Extracting entity information.} The information regarding the entity must be extracted from the source. 
\item{Associating entity and temporal information.} Given the entity and temporal information, an association between the two must be formed in order to generate event descriptions.
\item{Refining results.} After extracting event descriptions, some analysis should be done to increase the quality of the results.
\end{description}

The following subsections describe the sub problems, why the problems were difficult, and our approach to each problem in more detail. When addressing each of the problems, web redundancy was taken into consideration.

\subsection{Web Redundancy}
In general, our approach to each of the extraction problems is to identify multiple extraction techniques and rank them according to their signal strength. In our approach, a strong signal is defined as a signal that when extracted produces content without false positives. For example, when extracting verbs from a sentence, a possible signal could be the statistical approximation of a verb's relative location within the sentence. This signal based on statistical approximations would be classified as a weaker signal in comparison to a signal based on rules that enumerate all of the possible verbs and verb usages in a language. 

There is a clear tradeoff between extracting weak versus strong signals. A strong signal produces less false positives and is therefore more precise than a weaker signal. However, the strong signals in our design are rule based and rely on writing a large number of rules in order to extract all of the available information. One of the key findings discovered as part of this research is that redundancy on the Web allows ChronoSearch to focus on only the strongest signals, even if the rule set is not exhaustive. ChronoSearch is designed to use the intuition that important events are widely reported on the internet and that at least one occurrence of an event will be extracted by our strongest signal. 

By focusing on the strongest signal, the precision of the results are increased. The evaluation in section \ref{sec:Evaluation} also shows that the recall percentage of this methodology is sufficient and even outperforms the baseline. Yet, there is still room for improving recall. Our future research plans to further increase the recall rate by focusing on weaker signals. 

\subsection{Extracting Temporal Information}
Extracting temporal information is difficult due to the multiple ways in which time can be associated with a data source. To further complicate the problem, ChronoSearch aims to extract temporal information from multiple source types such as social networking sites, news sites, and blogs, without having prior knowledge of the structure or data type itself. For instance, a given source can specify time in various combinations of numbers and/or letters, such as: 04/05/1999, 1-1-82, May 1, 1989, yesterday, last week, 2001, etc.

During the design phase it was decided that absolute dates represented the strongest signals. Relative dates required associating a relative date to an absolute date in the document which is less precise than resolving absolute dates. To extract multiple forms of dates, ChronoSearch is designed to contain multiple regular expressions to match and resolve all of the different formats used to describe dates. 

\subsection{Extracting Entity Information}
Extracting information relevant to an entity involves detecting sentences that mention the entity. This problem can be difficult because the entities' absolute identifier, e.g. John Smith, is not always used when the entity is referenced. Pronouns such as he/she are often used to describe entities as well as the first or last name alone. Resolving pronouns was considered during our initial approach. However, the stronger signal, an absolute name, was chosen because of ChronoSearch's utilization of web redundancy.

\subsection{Association}
Associating an entity, event description, and time is the most difficult of the four sub problems. This sub problem requires some language semantic knowledge and careful extraction from the data source to pick out the correct time information and map it to the appropriate subject. For example, a source may contain X number of time specifications and only Y instances of the entity we are querying for, such that Y $<$ X. In this difficult scenario, the system must correctly associate the time information and events that are related to the query item.

To solve this problem, ChronoSearch associates an entity, temporal information, and an event using sentence boundaries. Therefore, Chonosearch selects sentences from Web documents that contain the input entity and an absolute date. The sentence boundary association was chosen as the strongest signal because of the level of precision provided. The way the English language is semantically structured, if an entity and a date are mentioned in the same sentence, the sentence is most probably describing an event that the entity is related to. 

There are several other approaches, such as a stack-based relative time approach mentioned in the future work section, but the sentence boundary approach was decided to be the strongest signal. 

\subsection{Refinement}
Once the event descriptions are generated, the precision of the events need to be refined by removing duplicate event descriptions, unimportant event descriptions, and descriptions that are not written concisely. Removing these sentences from the results is critical in improving the user experience. Again, the primary goal of ChronoSearch is to provide a visual overview of an entity that allows the user to quickly learn a complete history about an entity. Having duplicate, invalid, and unimportant results impairs the user’s analysis process because they are forced to spend time analyzing irrelevant results or the same result multiple times. 

Event descriptions describing the same event are removed using a two-pronged approach. Simply removing sentences that were exact copies is not sufficient because several event descriptions can describe the same event but in slightly different words. To address this problem, the cosine similarity test is used to remove paraphrased sentences. While a number of attempts at improving the measurement of textual overlap have been made in the research community, the vector space model used by the cosine similarity approach has achieved the best results to date \cite{kumaran2004text}. Where the cosine similarity test is unable to detect duplicate event descriptions, ChronoSearch is designed to utilize a verb similarity test. For example, there could be two sentences that describe the birth of an entity but only have one word in common, “born”. The cosine similarity test is unlikely to detect these types of duplicate event descriptions due to their wording, so a verb based similarity test is also used. Sentences with a verb set that have an overlap greater  than 50\% are removed. Verbs are selected for this test based on the intuition that event descriptions in the English language utilize verbs to describe an event.
 
ChronoSearch is also designed to remove event descriptions that do not conform to standard English sentence formats. This refinement is needed due to the extraction of information from the Web. While tools are employed to extract only textual content, there are still an abundance of extracted results that do not form a concise sentence. To sanitize the output, the average length of each word in the sentence is compared to the standard word lengths for English sentences written by people with writing levels between 8 years old and those at the college level. Using the average word length ranges specified in \cite{Ackerman:2010:Online}, event descriptions with average word lengths outside of a 3.0 to 7.2 range are removed.

To improve the precision of the results, ChronoSearch was also designed to remove unimportant results. The guiding principal for this approach was based on the intuition that the Web caters to user’s interest. The more popular an event description is on the Web, the more important the event is, and therefore more likely it is to be in a user’s expected results. To identify unimportant events, each result was searched for using the Bing search engine. However, the search results alone did not provide a sufficient correlation to determine whether or not an event description was important. See Section \ref{sec:LessonsLearned} on lessons learned for more details.

